#include <iostream>
#include <string>
#include <array>
#include <vector>

void genNextArr(std::string parent,std::vector<int>& nextArr)
{
    nextArr.resize(parent.length());
    nextArr.at(0)=0;
    nextArr.at(1)=0;
    int j=0;
    for(int i=2;i<parent.length();i++)
    {
        while(j!=0 && parent.at(j)!=parent.at(i-1))  //执行回溯
            j=nextArr.at(j);
        if(parent.at(j)==parent.at(i-1))
            j++;
        nextArr[i]=j;
    }
}

int kmp(std::string txt,std::string parrent)
{
    if(parrent.length()>txt.length())
        return -1;
    std::vector<int> nextArr;
    genNextArr(parrent,nextArr);
    int j=0;
    for(int i=0;i<txt.length();i++)
    {
        while (j>0 && txt.at(i)!=parrent.at(j))
            j=nextArr.at(j);
        if(txt.at(i)==parrent.at(j))
            j++;
        if(j==parrent.length())
            return i-parrent.length()+1;
    }
    return -1;
}

int main()
{
    std::cout<<kmp("ATGTGAGCTGGTGTGTGCFAA","GTGTGCF")<<std::endl;
    std::cout<<kmp("sssddddeeeer","sssddddeeaar")<<std::endl;
    std::cout<<kmp("aaaaaaaaaaaab","aab")<<std::endl;
    std::cout<<kmp("aadskckf","aadsk")<<std::endl;
    std::cout<<kmp("dads","dadsdhacrf")<<std::endl;
}